package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ListNode;
import com.cuz.daileetcode.utils.ListNodeUtils;

public class Day28 {


    /**
     * 根据输入k 将链表分割为小于等于大于三部分，
     * 并且保证相对顺序不变
     *
     *
     * @param head
     * @param value
     * @return
     */
    public static ListNode partitionLinkedListByValue(ListNode head, int value) {
        //如果没用节点 or 一个节点，直接return
        if (head == null || head.next == null) {
            return head;
        }
        //小于value的头和尾
        ListNode lessThenHead = null;
        ListNode lessThenTail = null;
        //等于value的头和尾
        ListNode equalHead = null;
        ListNode equalTail = null;
        //大于value的头和尾
        ListNode greaterThenHead = null;
        ListNode greaterThenTail = null;
        //循环遍历节点
        while (head != null) {
            //如果值小于value
            if (head.val < value) {
                //头为空，代表这是第一个小于value的节点， 那么头尾都指向这个节点
                if (lessThenHead == null) {
                    lessThenHead = head;
                    lessThenTail = head;
                } else {
                    //不是第一次了 那么 尾巴下一个指向这个节点
                    lessThenTail.next = head;
                    //尾巴移动
                    lessThenTail = lessThenTail.next;
                }
            }
            if (head.val == value) {
                if (equalHead == null) {
                    equalHead = head;
                    equalTail = head;
                } else {
                    equalTail.next = head;
                    equalTail = equalTail.next;
                }
            }
            if (head.val > value) {
                if (greaterThenHead == null) {
                    greaterThenHead = head;
                    greaterThenTail = head;
                } else {
                    greaterThenTail.next = head;
                    greaterThenTail = greaterThenTail.next;
                }
            }
            head = head.next;
        }
        ListNode newHead;
        //小于右节点
        if (lessThenHead != null) {
            newHead = lessThenHead;
            //等于部分有
            if (equalHead != null) {
                //小于连接等于
                lessThenTail.next = equalHead;
                //如果大于也有 等于连接大于
                if (greaterThenHead != null) {
                    equalTail.next = greaterThenHead;
                }
            }
            //小于部分没用 那么头就是等于部分
        } else if (equalHead != null) {
            newHead = equalHead;
            //有大于部分那就连接
            if (greaterThenHead != null) {
                equalTail.next = greaterThenHead;
            }
        } else {
            //小于等于都没，那直接连接大于部分就可以
            newHead = greaterThenHead;
        }
        return newHead;
    }


    public static void main(String[] args) {
        ListNode head = ListNodeUtils.listGenerate(2, 5, 5, 3, 4, 1, 0, 9);
        ListNode node = partitionLinkedListByValue(head, 5);
        ListNodeUtils.printList(node);
        ListNodeUtils.printList(head);
    }
}
